/*
 * File:   Solver.cpp
 * Author: gizmo
 *
 * Created on September 26, 2010, 2:26 PM
 */

#include "Solver.h"
#include "settings.h"
#include "mpi.h"
//#include <mpi/mpi.h>

/**
 * Empty
 */
Solver::Solver() {
}

/**
 * Empty
 * @param orig
 */
Solver::Solver(const Solver& orig) {
}

/**
 * Using graph's max cut weight information a temporary best solution is filled
 * @param gGraph
 */
void Solver::init(Graph* gGraph, int rank, int total) {
    graph = gGraph;
    process_rank = rank;
    processes = total;

    bestSolution.init(graph); // prepare initial best solution // TODO might be probably optimized
    bestSolution[graph->getMaxCutWeightNode()] = 1;
    bestSolution.countCost();
}

/**
 * Empty
 */
Solver::~Solver() {
}

void Solver::startClock() {
    start = MPI_Wtime();
}

void Solver::endClock() {
    end = MPI_Wtime();
}

double Solver::getRunningTime() const {
    return end - start;
}

/**
 * Core method of whole problem solving. All magic happens here.
 * Firstly, basic states including one node are created and pushed in stack.
 * Then a loop checking emptiness of the stack is launched.
 * In every iteration, a state is compared to best solution and then is
 * expanded using nextNode field.
 */
void Solver::solve() {
    // fill stack with basic states
    unsigned int i;
    /* MPI helpers*/
    int portionSize = 0, counter = 0, flag = 0;
    /* helper vars */
    int lastContactedProcess = process_rank;
    int noWorkResponsesCount = 0, color = COLOR_WHITE, noMessagesCounter = 0;
    /* work flags */
    bool keepWorking = true, workRequested = false;
    bool terminate = false, sendToken = false;
    int tokenToBeSent = COLOR_WHITE;
    MPI_Status status;
    unsigned int nc = graph->getNodeCount();
    unsigned char * buffer = new unsigned char[BUFFER_SIZE];

    /* stats vars */
    int stateCounter = 0, workRequestSentCounter = 0, noWorkResponseCounter = 0, workResponseCounter = 0;
    int whiteTokenSentCounter = 0, blackTokenSentCounter = 0;
    int workRequestServedCounter = 0;

    // basic states, only root!
    MPI_Barrier(MPI_COMM_WORLD);
    if (process_rank == 0) {
        startClock();
        for (i = 0; i < nc - 1; i++) { // nc -1 for optimization reasons, only half of states (1100 == 0011) is then generated
            State st;
            st.init(graph);
            st[i] = true;
            st.setNextNode(i + 1);
            st.countCost();
            myStack.push(st);
        }

        // root distributes work
        unsigned int distributing = (unsigned int) myStack.size() / processes;
        for (i = 1; i < processes; i++) {
            Stack division = myStack.divide(distributing);
            portionSize = division.serialize(buffer, BUFFER_SIZE);
            if (portionSize == -1) {
                cout << "!!!  SMALL BUFFER  !!!" << endl;
                return;
            }

            MPI_Send(buffer, portionSize, MPI_UNSIGNED_CHAR, i, MSG_WORK_RESPONSE, MPI_COMM_WORLD);
#ifdef MPI_DEBUG
            cout << process_rank << ": Sent array of size " << portionSize << " to " << i << endl;
#endif
        }
    } else { // no root
        // processes gather work
        MPI_Recv(buffer, BUFFER_SIZE, MPI_UNSIGNED_CHAR, 0, MSG_WORK_RESPONSE, MPI_COMM_WORLD, &status);
        MPI_Get_count(&status, MPI_UNSIGNED_CHAR, &portionSize);
        myStack.deserialize(buffer, portionSize, graph);
    }

    /**
     * Everyone has work, let's do some counting
     */

    while (keepWorking) {
        ++counter;
        if (!myStack.empty()) { // we have some states
            State current = myStack.top();
            myStack.pop();
            ++stateCounter;
            current.countCost();
#ifdef SHOW_STATES
            cout << process_rank << ':' << current;
#endif
            if (current.getCost() > 0 && current.getCost() <= bestSolution.getCost()) {
                bestSolution = current;
            }

            // expand to all possible states
            for (i = current.getNextNode(); i < nc; i++) {
                if (i + 1 == nc) continue;
                State st = State(current);
                st[i] = true;
                st.setNextNode(i + 1);
                myStack.push(st);
            }
        }

        if (counter % MSG_CHECK_INTERVAL == 0) {
            if (myStack.empty() && !workRequested) { // i am idle
                if (sendToken) {
                    sendToken = false;
                    if (tokenToBeSent == COLOR_WHITE && color == COLOR_WHITE) {
                        MPI_Send(buffer, MSG_SIGNAL_LENGTH, MPI_UNSIGNED_CHAR, (process_rank + 1) % processes, MSG_WHITE_TOKEN, MPI_COMM_WORLD);
                        ++whiteTokenSentCounter;
#ifdef MPI_ADUV_DEBUG
                        cout << process_rank << ": MSG_WHITE_TOKEN sent to " << (process_rank + 1) % processes << endl;
#endif
                    } else {
                        MPI_Send(buffer, MSG_SIGNAL_LENGTH, MPI_UNSIGNED_CHAR, (process_rank + 1) % processes, MSG_BLACK_TOKEN, MPI_COMM_WORLD);
                        ++blackTokenSentCounter;
#ifdef MPI_ADUV_DEBUG
                        cout << process_rank << ": MSG_BLACK_TOKEN sent to " << (process_rank + 1) % processes << endl;
#endif
                    }
                    color = COLOR_WHITE;
                }

                if (terminate) {
                    terminate = false;
                    for (i = 1; i < processes; i++) {
                        MPI_Send(buffer, MSG_SIGNAL_LENGTH, MPI_UNSIGNED_CHAR, i, MSG_TERMINATE, MPI_COMM_WORLD);
#ifdef MPI_ADUV_DEBUG
                        cout << process_rank << ": MSG_TERMINATE sent to " << i << endl;
#endif
                    }
                    keepWorking = false;
                }

                // call for work
                lastContactedProcess = (lastContactedProcess + 1) % processes;
                if (lastContactedProcess == process_rank) {
                    lastContactedProcess = (lastContactedProcess + 1) % processes;
                }
                MPI_Send(buffer, MSG_SIGNAL_LENGTH, MPI_UNSIGNED_CHAR, lastContactedProcess, MSG_WORK_REQUEST, MPI_COMM_WORLD);
                workRequested = true;
                ++workRequestSentCounter;
#ifdef MPI_DEBUG
                cout << process_rank << ": MSG_WORK_REQUEST sent to " << lastContactedProcess << endl;
#endif
            }

            MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
            if (flag) { // we have message, receive it
                MPI_Recv(buffer, BUFFER_SIZE, MPI_UNSIGNED_CHAR, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
            } else { // no message, continue in loop
                ++noMessagesCounter;
                continue;
            }

            Stack division;
            switch (status.MPI_TAG) {
                case MSG_WORK_REQUEST:
                    if (myStack.empty()) {
                        MPI_Send(buffer, MSG_SIGNAL_LENGTH, MPI_UNSIGNED_CHAR, status.MPI_SOURCE, MSG_NO_WORK_RESPONSE, MPI_COMM_WORLD);
#ifdef MPI_DEBUG
                        cout << process_rank << ": MSG_NO_WORK_RESPONSE sent to " << status.MPI_SOURCE << endl;
#endif
                    } else {
                        division = myStack.divide(processes / 2);
                        if (division.empty()) {
                            MPI_Send(buffer, MSG_SIGNAL_LENGTH, MPI_UNSIGNED_CHAR, status.MPI_SOURCE, MSG_NO_WORK_RESPONSE, MPI_COMM_WORLD);
#ifdef MPI_DEBUG
                            cout << process_rank << ": MSG_NO_WORK_RESPONSE sent to " << status.MPI_SOURCE << ", empty division" << endl;
#endif
                        } else {
                            portionSize = division.serialize(buffer, BUFFER_SIZE);
                            MPI_Send(buffer, portionSize, MPI_UNSIGNED_CHAR, status.MPI_SOURCE, MSG_WORK_RESPONSE, MPI_COMM_WORLD);
#ifdef MPI_DEBUG
                            cout << process_rank << ": MSG_WORK_RESPONSE (size: " << portionSize << ") sent to " << status.MPI_SOURCE << endl;
#endif
                            if (process_rank > status.MPI_SOURCE) {
                                color = COLOR_BLACK;
                            }
                        }
                    }
                    ++workRequestServedCounter;
                    break;
                case MSG_NO_WORK_RESPONSE:
                    workRequested = false;
                    ++noWorkResponsesCount; // local, till work comes
                    ++noWorkResponseCounter; // total
                    if (process_rank == 0 && noWorkResponsesCount > processes - 1) {
                        sendToken = true;
                        tokenToBeSent = COLOR_WHITE;
                    }
#ifdef MPI_DEBUG
                    cout << process_rank << ": MSG_NO_WORK_RESPONSE received from " << status.MPI_SOURCE << endl;
#endif
                    break;
                case MSG_WORK_RESPONSE:
                    workRequested = false;
                    ++workResponseCounter;
                    noWorkResponsesCount = 0;
                    MPI_Get_count(&status, MPI_UNSIGNED_CHAR, &portionSize);
                    myStack.deserialize(buffer, portionSize, graph);
#ifdef MPI_DEBUG
                    cout << process_rank << ": MSG_WORK_RESPONSE received from " << status.MPI_SOURCE << endl;
#endif
                    break;
                case MSG_BLACK_TOKEN:
                    sendToken = true;
                    if (process_rank == 0) {
                        tokenToBeSent = COLOR_WHITE;
                    } else {
                        tokenToBeSent = COLOR_BLACK;
                    }
#ifdef MPI_ADUV_DEBUG
                    cout << process_rank << ": MSG_BLACK_TOKEN received from " << status.MPI_SOURCE << endl;
#endif
                    break;
                case MSG_WHITE_TOKEN:
                    if (process_rank == 0) {
                        terminate = true;
                    } else {
                        sendToken = true;
                        tokenToBeSent = color;
                    }
#ifdef MPI_ADUV_DEBUG
                    cout << process_rank << ": MSG_WHITE_TOKEN received from " << status.MPI_SOURCE << endl;
#endif
                    break;
                case MSG_TERMINATE:
                    keepWorking = false;
#ifdef MPI_ADUV_DEBUG
                    cout << process_rank << ": MSG_TERMINATE received from " << status.MPI_SOURCE << endl;
#endif
                    break;
                default:
                    break;
            }
        }
    }

    // gather solution
    if (process_rank == 0) { // root

        State ** allBestSolutions = new State *[processes];
        allBestSolutions[0] = &getBestSolution();

        State * st;
        for (i = 1; i < processes; i++) {
            MPI_Recv(buffer, BUFFER_SIZE, MPI_UNSIGNED_CHAR, i, MSG_BEST_SOLUTION, MPI_COMM_WORLD, &status);
            MPI_Get_count(&status, MPI_UNSIGNED_CHAR, &portionSize);
            st = new State();
            st->init(graph);
            st->deserialize(buffer, portionSize);
            st->countCost();
            allBestSolutions[i] = st;
        }

        // compare all solutions
        int best = 0;
        for (i = 0; i < processes; i++) {
            if ((*allBestSolutions[i]).getCost() < (*allBestSolutions[best]).getCost()) {
                best = i;
            }
#ifdef MPI_DEBUG
            cout << i << ": MSG_BEST_SOLUTION : " << *allBestSolutions[i];
#endif
        }
        // assign best solution
        bestSolution = *allBestSolutions[best];
        delete [] allBestSolutions;

    } else {
        portionSize = getBestSolution().serialize(buffer, BUFFER_SIZE);
        MPI_Send(buffer, portionSize, MPI_UNSIGNED_CHAR, 0, MSG_BEST_SOLUTION, MPI_COMM_WORLD);
#ifdef MPI_DEBUG
        cout << process_rank << ": MSG_BEST_SOLUTION sent to root " << endl;
#endif
    }

#ifdef SHOW_TOTAL_STATS
    cout << process_rank << ':' << " State count: " << stateCounter << endl;
    cout << process_rank << ':' << " Work requests sent count: " << workRequestSentCounter << endl;
    cout << process_rank << ':' << " Work requests served count: " << workRequestServedCounter << endl;
    cout << process_rank << ':' << " No work responses recieved count: " << noWorkResponseCounter << endl;
    cout << process_rank << ':' << " Work responses recieved count: " << workResponseCounter << endl;
    cout << process_rank << ':' << " White token sent count: " << whiteTokenSentCounter << endl;
    cout << process_rank << ':' << " Black token sent count: " << blackTokenSentCounter << endl;
#endif

    MPI_Barrier(MPI_COMM_WORLD);

    if (process_rank == 0) { // root
        endClock();
    }

}

/**
 *
 * @return best Solution
 */
State & Solver::getBestSolution() {
    return bestSolution;
}

